#include <stdio.h>
#include <malloc.h>
#define MAX_QUEUE_SIZE 100
#define ERROR 2
#define OK 1
typedef int ElemType;
typedef int Status;

/*
	一：
	1.先加元素再动指针
	  先按rear的位置存入，在rear++
	2.队尾指针rear指的是队尾后空一位

	3.出队时先将下标为front的元素取出，再将front减1
	4.队头指的时实际的位置

	二：
	1.动指针再加元素
	  进队时先让队尾进一，再将新元素按rear指示加入
	2.队尾指针rear指的时队尾实际的位置

	3.入队时将队头指针进一，再将front指向的元素取出
	4.队头指针指的是实际队头的前一位置
*/
/*
	队首指针front，队尾指针rear，分别指向队首队尾

	初始化:front = rear = 0
	入队:新元素插入rear所指的位置，然后rear+1
	出队:删去front所指的元素,然后加1并返回被删元素
	为空：front = rear
	队满 rear = MAX_QUEUE_SIZE - 1

	解决假溢出  循环队列 求模 i = (i+1)%MAX_QUEUE_SIZE

	或者 if(i+1 == MAX_QUEUE_SIZE)
			i = 0
		else
			i++

	需要改变队满条件  (rear + 1)/%长度 == front
	判断元素个数 (rear - front + 模（长度）)/模
	rear - front + 模 计算有跨越的个数，取余计算没跨越的个数
	判断满 空间需要被牺牲一个

	入队，先赋值在前进，即尾部指针指向的最后一个元素的后一个
	出队，先赋值再前进，即头部指针指向第一个元素
*/

typedef struct queue
{
	ElemType Elem_array[MAX_QUEUE_SIZE];
	int front;  //头部，出去的地方
	int rear;  //尾部，进入的地方 
}SqQueue;

//初始化循环队列
SqQueue Init_CirQueue(void)
{
	SqQueue Q;
	Q.front = Q.rear = 0;
	return Q;
}

//入队
Status Insert_CirQueue(SqQueue Q,ElemType e)
{
	//将元素e插入到队尾rear,牺牲了一个空间先进行判断是否满了，先赋值，指针再前进
	if ((Q.rear + 1)%MAX_QUEUE_SIZE == Q.front)
		return ERROR;
	Q.Elem_array[Q.rear] = e;
	Q.rear = (Q.rear + 1)%MAX_QUEUE_SIZE;

	return OK;
}

//出队
Status Delete_CirQueue(SqQueue Q,ElemType *x)
{
	//出队先判断是否为空，先赋值,指针再前进
	if (Q.front == Q.rear)
		return ERROR;
	*x = Q.Elem_array[Q.front];
	Q.front = (Q.front + 1)%MAX_QUEUE_SIZE;

	return OK;
}



/*
	采用count变量标志队列是否为满，仅知道队头指针front
	和队列中元素个数count，设计出这中循环队列的初始化
	入队 出队的算法

	队列为空时，判断count是否为0，所以不用牺牲一个空间
	可以存放满

	已知front和count求rear
	(front + count)%MAX_SIZE

	已知 rear,count 求front
	(rear - count + MAXSIZE)&MAXSIZE

	入队，指针先前进再赋值，即队尾是指向的最后一个元素
	出队，指针先前进再赋值，即头是在队头的前一个位置
	count判断队空不需要牺牲空间
*/
typedef struct sqqueue1
{
	ElemType Elem_array[MAX_QUEUE_SIZE];
	int front;
	int count;
}SqQueue1;

//初始化
void Init_CirQueue1(SqQueue1 *Q)
{
	Q = (SqQueue1 *)malloc(sizeof(SqQueue1));
	Q -> front = 0;
	Q -> count = 0;
}

//入队
Status Insert_CirQueue1(SqQueue1 *Q,ElemType e)
{
	int rear;  //临时队尾指针,用公式赋值
	if (Q -> count == MAX_QUEUE_SIZE)
		return ERROR;
	else
	{
		rear = (Q -> front + Q -> count)%MAX_QUEUE_SIZE;
		rear = (rear + 1)%MAX_QUEUE_SIZE;
		Q -> Elem_array[rear] = e;
		Q -> count++;
		return OK;
	}
}

//出队
Status Delete_CirQueue1(SqQueue1 *Q,ElemType *e)
{
	if (Q -> count == 0)
		return ERROR;
	else
	{
		Q -> front = (Q -> front + 1)%MAX_QUEUE_SIZE;
		*e = Q -> Elem_array[Q -> front];
		Q -> count--;
		return OK;
	}
}

//判断是否为空
Status QueueEmpty(SqQueue1 *Q)
{
	return Q -> count == 0;
}

/*
	使用tag，值为0或1区分队满还是对空，因为只有进队才会导致队满，进队则tag为1
	只有出队会导致队空
	初始tag=0，rear=0 front=0
	队空条件:Q.front = Q.rear 且 	Q.tag == 0
	队满条件:Q.front = Q.rear 且 	Q.tag == 1
	进队:先赋值，指针在前进
	出队:先赋值，指针在前进
	tag判断队空不需要牺牲一个空间
*/
typedef struct sqqueue2
{
	ElemType Elem_array[MAX_QUEUE_SIZE];
	int front;
	int rear;
	int tag;
}SqQueue2;

Status Insert_CirQueue2(SqQueue2 *Q,ElemType e)
{
	//入队先判断是否队满,先赋值指针前进
	if (Q ->front == Q -> rear && Q -> tag == 1)
		return ERROR;
	Q -> Elem_array[Q -> rear] = e;
	Q -> rear = (Q -> rear + 1)%MAX_QUEUE_SIZE;
	Q -> tag = 1;

	return OK;
}

Status Delete_CirQueue2(SqQueue2 *Q,ElemType *e)
{
	//出队先判断是否为空，先赋值，指针再前进
	if (Q -> front == Q -> rear && Q -> tag ==0)
		return ERROR;
	*e = Q -> Elem_array[Q -> front];
	Q -> front = (Q -> front + 1)%MAX_QUEUE_SIZE;
	Q -> tag = 0;

	return OK;
}

int main()
{}